/**
 * @constructor
 * @param {number} val
 * @param {ListNode|null} [next]
 */
function ListNode(val, next) {
    /** @type {number} */
    this.val = (val === undefined ? 0 : val)
    /** @type {ListNode|null} */
    this.next = (next === undefined ? null : next)
}

var isPalindrome = function (head) {
    let stack = [];
    let curr = head;

    // Step 1: 把所有节点值压入栈
    while (curr) {
        stack.push(curr.val);
        curr = curr.next;
    }

    // Step 2: 再次遍历链表，对比栈顶元素
    curr = head;
    while (curr) {
        if (curr.val !== stack.pop()) {
            return false;
        }
        curr = curr.next;
    }

    return true;
};
